class Solution {
public:
    bool isValid(const string &ip) {
        if (ip.length() == 0 || ip.length() > 3) {
            return false;
        } else {
            if (ip.length() > 1 && ip[0] == '0') {
                return false;
            }
            int value = atoi(ip.c_str());
            if (!(0 <= value && value <= 255)) {
                return false;
            }
        }
        return true;
    }

    vector<string> restoreIpAddresses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = s.length();
        vector<string> ans;

        // [0, i], [i + 1, j], [j + 1, k], [k + 1, n - 1]
        for (int i = 0; i < 3 && i < n; ++i) {
            if (!isValid(s.substr(0, i - 0 + 1))) {
                continue;
            }
            for (int j = i + 1; j < i + 4 && j < n; ++j) {
                if (!isValid(s.substr(i + 1, j - i))) {
                    continue;
                }
                for (int k = j + 1; k < j + 4 && k < n - 1; ++k) {
                    if (!isValid(s.substr(j + 1, k - j))) {
                        continue;
                    }
                    if (!isValid(s.substr(k + 1))) {
                        continue;
                    }
                    string ip = s.substr(0, i - 0 + 1) + "." +
                                s.substr(i + 1, j - i) + "." +
                                s.substr(j + 1, k - j) + "." +
                                s.substr(k + 1);
                    ans.push_back(ip);
                }
            }
        }
        return ans;
    }
};
